package class006;

import java.util.Arrays;

// 有序数组中找<=num的最右位置
public class Code03_FindRight {

	// 为了验证


	// 为了验证
	public static int[] randomArray(int n, int v) {
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = (int) (Math.random() * v) + 1;
		}
		return arr;
	}

	// 为了验证
	// 保证arr有序，才能用这个方法
	public static int right(int[] arr, int num) {
		for (int i = arr.length - 1; i >= 0; i--) {
			if (arr[i] <= num) {
				return i;
			}
		}
		return -1;
	}

	// 保证arr有序，才能用这个方法
	// 有序数组中找<=num的最右位置
	public static int findRight(int[] arr, int num) {
		int l = 0, r = arr.length - 1, m = 0;
		int ans = -1;
		while (l <= r) {
			m = l + ((r - l) >> 1);
			if (arr[m] <= num) {
				ans = m;
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		return ans;
	}


	// 保证arr有序，才能用这个方法
	// 有序数组中找 == num的最右位置

	public static int findRightEqu(int[] arr, int num){
		int l = 0, r = arr.length -1;
		int ans = 0;
		while (l <= r){
			int mid = l + ((r-l) >> 1);
			if(arr[mid] <= num){
				ans = mid;
				l = mid + 1;
			}else {
				r = mid - 1;
			}
		}
		return arr[ans] == num ? ans : -1;
	}

	public static void main(String[] args) {
		int[] arr= {1,3,4,4,4,12,17,17,21};
		int right = findRight(arr, 4);
		int rightEqu = findRightEqu(arr, 4);

		System.out.println(right);
		System.out.println(rightEqu);

	}



}
